跳到主要内容

(COCI 2023/2024 5) Piratski kod

· 阅读需 4 分钟

题解​

题意​

给定一个长度nn，分别求每一个长度为k(k≤n)k(k \leq n)的所有可能的二进制序列的权值总和。

定义一个二进制串的权值

将二进制串分为若干个子串满足： 对于除了末尾外的子串，每个子串以一对连续11结尾且仅含有一对连续11。

定义长度为kk的子串ss的权值为 ∑i=1k−1si⋅fibi+1\sum_{i=1}^{k-1} s_i \cdot fib_{i+1}

fibfib定义

fib1=1,fib2=1,fibi=fibi−1+fibi−2(i>2)fib_1=1,fib_2=1,fib_i=fib_{i-1}+fib_{i-2}(i > 2)

那么该二进制串的权值为，分割后含连续11的子串的权值和

范围：n≤5000n \leq 5000

解法​

考虑dpdp

难点在于设计状态。

首先我们观察到我们子串的权值由两部分组成： 含连续11的串(以下称：整块)，不含连续11的串(以下称：散块)

而每一个二进制串的权值由一个整块和一个散块组成。

于是我们可以设计状态fif_i表示长度为ii的整块的权值总和。gi,1/0g_{i,1/0}表示以1/01/0结尾的散块的权值总和。

首先考虑散块的权值总和，由于末尾0不产生贡献。

gi,0=gi−1,1+gi−1,0g_{i,0}=g_{i-1,1}+g_{i-1,0}

考虑末尾的11会对所有序列产生贡献，所以贡献要乘上序列总数

gi,1=gi−1,0+fibi+1⋅numgi−1,0g_{i,1}=g_{i-1,0}+fib_{i+1} \cdot numg_{i-1,0}

numgi,0=numgi−1,1+numgi−1,0numg_{i,0}=numg_{i-1,1}+numg_{i-1,0}

numgi,1=numgi−1,0numg_{i,1}=numg_{i-1,0}

接下来考虑整块的权值和，整块可以由一个整块，一个散块和一个末尾数字1组成

fi=∑j=1i−1gi,1⋅numfi−j−1+fi−j−1⋅numgj,1f_i=\sum_{j=1}^{i-1} g_{i,1} \cdot numf_{i-j-1}+f_{i-j-1} \cdot numg_{j,1}

numfi=∑j=1i−1numgj,1⋅numfi−j−1numf_i=\sum_{j=1}^{i-1}numg_{j,1} \cdot numf_{i-j-1}

那么答案就是 ansi=∑j=2ifj⋅(numgi−j,0+numgi−j,1)ans_i=\sum_{j=2}^{i}f_j \cdot (numg_{i-j,0}+numg_{i-j,1})

代码​

code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
const int N=5e3+10;
int n;
ll fib[N];
ll f[N],g[N][2],numf[N],numg[N][2];
ll ans[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    fib[1]=1;
    fib[2]=1;
    for(int i=3;i<=n+1;i++) fib[i]=(fib[i-1]+fib[i-2])%mod;
    numg[0][0]=1;
    numf[0]=1;
    for(int i=1;i<=n;i++)
    {
        numg[i][0]=(numg[i-1][0]+numg[i-1][1])%mod;
        numg[i][1]=(numg[i-1][0])%mod;
        g[i][0]=(g[i-1][1]+g[i-1][0])%mod;
        g[i][1]=(g[i-1][0]+numg[i-1][0]*fib[i+1]%mod)%mod;
        for(int j=1;j<=i-1;j++)
        {
            ans[i]=(ans[i]+f[j]*(numg[i-j][0]+numg[i-j][1])%mod)%mod;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            numf[i]=(numf[i]+numg[j][1]*numf[i-j-1]%mod)%mod;
            f[i]=(f[i]+g[j][1]*numf[i-j-1]%mod+f[i-j-1]*numg[j][1]%mod)%mod;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j<=i;j++)
        {
            ans[i]=(ans[i]+f[j]*(numg[i-j][0]+numg[i-j][1])%mod)%mod;
        }
        cout<<ans[i]<<' ';
    }
    return 0;
}